#include<stdio.h>
#include<stdlib.h>
int quicksort(int *a,int p,int r)
{
	int q;
	if(p<r)
	{
		q=partition(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q,r);
	}
	return 0;
}

int partition(int *a,int p,int r)
{
	int i,j,k;
	int temp,x;
	int q;
	q=(r+p)/2;
	x=a[q];
	i=p;
	j=r;
	while(i<j)
	{
		while(a[i]<x) i++;
		while(a[j]>=x) j--;
		if(i<j)
		{
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	if(i==p)
	{
		temp=a[i];
		a[i]=x;
		a[q]=temp;
		return (i+1);
	}
	return i;
}



int main()
{
	int i,j,k;
	int a[20]={3,5,2,6,8,2,1,7,3,9,12,31,2,4,5,8,1,10,3,15};
	quicksort(a,0,19);
	for(i=0;i<20;i++) printf("%d ",a[i]);
	printf("\n");
	return 0;
}
